package com.platform.modules.alg.alglib.poj3635;

import java.util.PriorityQueue;

public class Poj3635 {
    public String output = "";
    private final int maxn = 1005;
    private final int maxm = 20005;
    edge edge[] = new edge[maxm];
    int head[] = new int[maxn];
    boolean vis[][] = new boolean[maxn][105];
    int n;
    int m;
    int V;
    int st;
    int ed;
    int cnt;
    int price[] = new int[maxn];

    public Poj3635() {
        for (int i = 0; i < edge.length; i++) {
            edge[i] = new edge();
        }
    }

    void add(int u, int v, int w) {
        edge[cnt].v = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }

    int bfs() {
        for (int i = 0; i < maxn; i++) {
            for (int j = 0; j < 105; j++) {
                vis[i][j] = false;
            }
        }
        PriorityQueue<node> Q = new PriorityQueue<>(); // 优先队列
        Q.add(new node(st, 0, 0));
        while (!Q.isEmpty()) {
            node cur = Q.peek();
            Q.poll();
            int u = cur.u, vol = cur.vol, cost = cur.cost;
            vis[u][vol] = true;
            if (u == ed) return cost;
            if (vol < V && !vis[u][vol + 1])
                Q.add(new node(u, vol + 1, cost + price[u]));
            for (int i = head[u]; i != -1; i = edge[i].next) {
                int v = edge[i].v, w = edge[i].w;
                if (vol >= w && !vis[v][vol - w])
                    Q.add(new node(v, vol - w, cost));
            }
        }
        return -1;
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        m = Integer.parseInt(words[1]);

        String[] pricestr = line[1].split(" ");
        for (int i = 0; i < n; i++) {
            price[i] = Integer.parseInt(pricestr[i]);
        }

        int u, v, w;
        cnt = 0;
        for (int i = 0; i < head.length; i++) {
            head[i] = -1;
        }

        for (int i = 0; i < m; i++) {
            String[] edgs = line[2 + i].split(" ");
            u = Integer.parseInt(edgs[0]);
            v = Integer.parseInt(edgs[1]);
            w = Integer.parseInt(edgs[2]);
            add(u, v, w);
            add(v, u, w);
        }

        int q = Integer.parseInt(line[2 + m]);
        for (int i = 0; i < q; i++) {
            String[] querys = line[3 + m + i].split(" ");
            V = Integer.parseInt(querys[0]);
            st = Integer.parseInt(querys[1]);
            ed = Integer.parseInt(querys[2]);
            int ans = bfs();
            if (ans == -1) output += "impossible";
            else {
                output += String.valueOf(ans) + "\n";
            }
        }
        return output;
    }
}

class edge {
    int v;
    int w;
    int next;
}

class node implements Comparable {
    int u;
    int vol;
    int cost;

    node(int u_, int vol_, int cost_) {
        u = u_;
        vol = vol_;
        cost = cost_;
    }

    @Override
    public int compareTo(Object o) {
        return this.cost - ((node) o).cost;
    }
}
